// ------------------------------------------------------------------------------------------------
// ---- Livro Algoritmos (de Cormen, Leiserson, Rivest, Stein) ------------------------------------
// ---- Algoritmos CountingSort e RadixSort (Capítulo 8) ------------------------------------------
// ------------------------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>

#include <stdbool.h>// bool,false,true
#include <time.h>   // time_t,time,difftime
#include <math.h>   // floor
#include <windows.h>// GetTickCount

void CountingSort(int* A, int p, int r, int K);
void RadixSort(double* A, int p, int r, int d1, int d2);

void imprimir_vetor(int* vetor, int N, char* filename);
void imprimir_vetor2(double* vetor, int N, char* filename);


int main() {
    int i,j;


    // Cria um vetor
    int K = 100000;
    int N = 1000000;
    int* vetor = (int*) calloc(N,sizeof(int));
    srand (time(NULL));
    for (i=0;i<N;i++) vetor[i] = rand()%K;

    imprimir_vetor(vetor,N,"entrada.txt");
    int t1 = GetTickCount();

    CountingSort(vetor,0,N-1, K);
    int t2 = GetTickCount();

    printf("CountingSort (%d miliseg)\n",t2-t1);
    imprimir_vetor(vetor ,N,"saida_counting.txt");
    free(vetor);



    N = 100000;
    double* vetor2 = (double*) calloc(N,sizeof(double));
    srand (time(NULL));
    for (i=0;i<N;i++) vetor2[i] = (double) 1000*rand()/RAND_MAX;

    imprimir_vetor2(vetor2,N,"entrada.txt");
    t1 = GetTickCount();

    RadixSort(vetor2,0,N-1, -6,6);
    t2 = GetTickCount();

    printf("RadixSort (%d miliseg)\n",t2-t1);
    imprimir_vetor2(vetor2 ,N,"saida_radix.txt");
    free(vetor2);
    return 0;
}



// ------------------------------------------------------------------------------------------------
// ---- Algoritmo COUNTING-SORT -------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
// --- Ordena um vetor A da posição p a r, supondo que A tenha só valores inteiros entre 0 e K
// ------------------------------------------------------------------------------------------------
void CountingSort(int* A, int p, int r, int K) {
    int i,j;
    int N = r-p+1;
    int* B = (int*) calloc(N,sizeof(int));
    int* C = (int*) calloc(K+1,sizeof(int));
    for (i=0; i<=K; i++) C[i] = 0;
    for (j=p; j<=r; j++) C[A[j]]++;
    for (i=1; i<=K; i++) C[i] = C[i]+C[i-1];
    for (j=r; j>=p; j--) B[--C[A[j]]] = A[j];
    for (j=p; j<=r; j++) A[j] = B[j-p];
    free(B); free(C);
}


// ------------------------------------------------------------------------------------------------
// ---- Algoritmo RADIX-SORT ----------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
// --- Ordena um vetor A da posição p a r, considerando a ordem dos digitos d1 a d2
// --- d1 <= d2 representam as casas decimais ...,2,1,0,-1,-2,...
// ------------------------------------------------------------------------------------------------
void RadixSort(double* A, int p, int r, int d1, int d2) {
    int i,j,d;
    int N = r-p+1;
    int K = 9;
    double* B = (double*) calloc(N,sizeof(double));
    int* C = (int*) calloc(K+1,sizeof(int));

    for (d=d1; d<d2; d++) {
        for (i=0; i<=K; i++) C[i] = 0;
        for (j=p; j<=r; j++) C[digito(A[j],d)]++;
        for (i=1; i<=K; i++) C[i] = C[i]+C[i-1];
        for (j=r; j>=p; j--) B[--C[digito(A[j],d)]] = A[j];
        for (j=p; j<=r; j++) A[j] = B[j-p];
    }
    free(B); free(C);
}

// retorna o dígito d do numero real valor
int digito(double valor, int d) {
    double mult = pow(10,-d-1);
    valor *= mult;
    int dig = 10 * (valor - floor(valor));
    return dig;
}

// ------------------------------------------------------------------------------------------------
// ---- Imprimir vetor em arquivo -----------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
void imprimir_vetor(int* vetor, int N, char* filename) {
    if (filename==NULL) filename="saida.txt";
	FILE* arq = fopen(filename,"w");
	int i;
    for (i=0;i<N;i++) fprintf(arq,"%d ",vetor[i]);
	fclose(arq);
}

void imprimir_vetor2(double* vetor, int N, char* filename) {
    if (filename==NULL) filename="saida.txt";
	FILE* arq = fopen(filename,"w");
	int i;
    for (i=0;i<N;i++) fprintf(arq,"%f ",vetor[i]);
	fclose(arq);
}